# https://leetcode.cn/problems/minimum-time-to-complete-trips/description/
# 2187. 完成旅途的最少时间
# medium, 刘小康 2024.09.13
# 二分查找

class Solution:
    def minimumTime(self, time: list[int], totalTrips: int) -> int:
        left = 1
        right = 1000000000000000
        while left < right:     # 下界
            target_time = left + ((right - left) >> 1)

            travel_times = 0
            for it in time:
                travel_times += self.times(target_time, it)

            if travel_times >= totalTrips:
                right = target_time
            else:
                left = target_time + 1

        return left

    @staticmethod
    def times(time, bus_time):
        return time // bus_time
